package com.thghh.ch6.graph;

import java.util.Queue;
import java.util.Stack;

/**
 * @author Zhikang.Peng
 * @version 1.0
 * @email thghh@qq.com
 * @date 2020/11/13 16:01
 */
public interface IGraphAlgorithm<T> {

    /**
     * 深度优先遍历
     *
     * @param origin 遍历的起点对象
     * @return
     */
    Queue<T> depthFirst(T origin);

    /**
     * 广度优先遍历
     *
     * @param origin 遍历的起点对象
     * @return
     */
    Queue<T> breadthFirst(T origin);

    /**
     * 执行有向无环图的顶点的后拓扑排序
     *
     * @return
     */
    Stack<T> topologicalSort();

    /**
     * 最短路径
     *
     * @param begin 起点
     * @param end   终点
     * @param path  该栈保存沿最短路径的顶点，起点标识位于栈顶,终点标识位于栈底
     * @return
     */
    int shortestPath(T begin, T end, Stack<T> path);

    /**
     * 寻找两个指定顶点费用最低的路径
     *
     * @param begin 起点
     * @param end   终点
     * @param path  该栈保存沿费用最低路径的顶点，起点标识位于栈顶,终点标识位于栈底
     * @return
     */
    double cheapesPath(T begin, T end, Stack<T> path);

}
